{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Subarrays With LCM Equal to K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subarrayLCM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小公倍数为 K 的子数组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，请你统计并返回 <code>nums</code> 的 <strong>子数组</strong> 中满足 <em>元素最小公倍数为 <code>k</code> </em>的子数组数目。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中一个连续非空的元素序列。</p>\n",
    "\n",
    "<p><strong>数组的最小公倍数</strong> 是可被所有数组元素整除的最小正整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,6,2,7,1], k = 6\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>以 6 为最小公倍数的子数组是：\n",
    "- [<em><strong>3</strong></em>,<em><strong>6</strong></em>,2,7,1]\n",
    "- [<em><strong>3</strong></em>,<em><strong>6</strong></em>,<em><strong>2</strong></em>,7,1]\n",
    "- [3,<em><strong>6</strong></em>,2,7,1]\n",
    "- [3,<em><strong>6</strong></em>,<em><strong>2</strong></em>,7,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3], k = 2\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在以 2 为最小公倍数的子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-subarrays-with-lcm-equal-to-k](https://leetcode.cn/problems/number-of-subarrays-with-lcm-equal-to-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-subarrays-with-lcm-equal-to-k](https://leetcode.cn/problems/number-of-subarrays-with-lcm-equal-to-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,2,7,1]\\n6', '[3]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res:\n",
    "                    break\n",
    "                if res == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math \n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        left, right =  0, 0\n",
    "        ans = 0\n",
    "        for r in range(len(nums)):\n",
    "            lcm = 1\n",
    "            for l in range(r, len(nums)):\n",
    "                lcm = math.lcm(lcm, nums[l])\n",
    "                # if k % lcm != 0:\n",
    "                #     break\n",
    "                if lcm == k:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            l = 1\n",
    "            for j in range(i, n):\n",
    "                l = lcm(l, nums[j])\n",
    "                if k % l: break\n",
    "                if k == l: ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        # res = 0\n",
    "        \n",
    "        # def lcm(a, b):\n",
    "        #     ac, bc = a, b\n",
    "        #     if a > b:\n",
    "        #         a, b = b, a\n",
    "        #     while b % a:\n",
    "        #         r = b % a\n",
    "        #         b, a = a, r\n",
    "        #     return ac * bc // a\n",
    "        # n = len(nums)\n",
    "        # for i in range(n):\n",
    "        #     l = 1\n",
    "        #     for j in range(i, n):\n",
    "        #         l = lcm(l, nums[j])\n",
    "        #         if k % l:\n",
    "        #             break\n",
    "        #         if k == l:\n",
    "        #             res += 1\n",
    "        # return res\n",
    "\n",
    "        ans = 0\n",
    "        a = []  # [LCM，相同 LCM 区间的右端点]\n",
    "        i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if k % x:  # 保证后续求的 LCM 都是 k 的因子\n",
    "                a = []\n",
    "                i0 = i\n",
    "                continue\n",
    "            a.append([x, i])\n",
    "            # 原地去重，因为相同的 LCM 都相邻在一起\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = lcm(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "            del a[j + 1:]\n",
    "            if a[0][0] == k:\n",
    "                ans += a[0][1] - i0\n",
    "        return ans\n",
    "\n",
    "        # ans = 0\n",
    "        # n = len(nums)\n",
    "        # pre = dict()\n",
    "        # for num in nums:\n",
    "        #     cur = dict()\n",
    "        #     if k % num == 0:\n",
    "        #         cur[num] = 1\n",
    "        #         for p in pre:\n",
    "        #             x = math.lcm(p, num)\n",
    "        #             if k % x == 0:\n",
    "        #                 cur[x] = cur.get(x, 0) + pre[p]\n",
    "        #         ans += cur.get(k, 0)        \n",
    "        #     pre = cur\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if k % nums[i]:\n",
    "                continue\n",
    "            for a in accumulate(nums[i:], lcm):\n",
    "                if a > k:\n",
    "                    break\n",
    "                if a == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break  # 剪枝：LCM 必须是 k 的因子\n",
    "                if res == k: ans += 1\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/number-of-subarrays-with-lcm-equal-to-k/solutions/1965427/by-endlesscheng-3qnt/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        #n=len(nums)\n",
    "        #ans=0\n",
    "        #for i in range(n):\n",
    "        #    res=1\n",
    "        #    for j in range(i,n):\n",
    "        #        res=lcm(res,nums[j])\n",
    "        #        if res==k: ans += 1\n",
    "        #return ans\n",
    "        a=[]\n",
    "        ans=0\n",
    "        i0=-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if k%x:\n",
    "                a=[]\n",
    "                i0=i\n",
    "                continue\n",
    "            a.append([x,i])\n",
    "            j=0\n",
    "            #[3,4][3,4]\n",
    "            for p in a:\n",
    "                p[0]=lcm(p[0],x)\n",
    "                if a[j][0]!=p[0]:\n",
    "                    j += 1\n",
    "                    a[j]=p\n",
    "                else:\n",
    "                    a[j][1]=p[1]\n",
    "            del a[j+1:]\n",
    "            if a[0][0]==k:\n",
    "                ans += a[0][1]-i0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for a in accumulate(nums[i:], lcm):\n",
    "                if a > k:\n",
    "                    break\n",
    "                if a == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for a in accumulate(nums[i:], lcm):\n",
    "                if a > k:\n",
    "                    break\n",
    "                if a == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "      ans,n = 0, len(nums)\n",
    "      for i in range(n): #外部循环，枚举子数组的起始位置\n",
    "        res = 1 #最小公倍数\n",
    "        for j in range(i,n): #内部循环，枚举子数组的结束位置\n",
    "          res = lcm(res, nums[j])\n",
    "          if k % res != 0: break #内部循环跳出后，直接开始下一轮的外部循环\n",
    "          if res == k: ans += 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "        print(lcm(3,4),gcd(3,4))##输出为12，1\n",
    "        '''\n",
    "        answer = 0\n",
    "        length = len(nums)\n",
    "        for i in range(length):\n",
    "            res = 1\n",
    "            for j in range(i,length):\n",
    "                res = lcm(res,nums[j])\n",
    "                if res == k :\n",
    "                    answer += 1 \n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res != 0: break\n",
    "                if res == k: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break  # 剪枝：LCM 必须是 k 的因子\n",
    "                if res == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        def lcm(a, b):\n",
    "            ac, bc = a, b\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            while b % a:\n",
    "                r = b % a\n",
    "                b, a = a, r\n",
    "            return ac * bc // a\n",
    "        \n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            for j in range(i, len(nums)):\n",
    "                if i == j:\n",
    "                    l = nums[j]\n",
    "                else:\n",
    "                    l = lcm(l, nums[j])\n",
    "                if l == k:\n",
    "                    res += 1\n",
    "                elif l > k:\n",
    "                    break\n",
    "        return res\n",
    "\n",
    "        # ans = 0\n",
    "        # n = len(nums)\n",
    "        # pre = dict()\n",
    "        # for num in nums:\n",
    "        #     cur = dict()\n",
    "        #     if k % num == 0:\n",
    "        #         cur[num] = 1\n",
    "        #         for p in pre:\n",
    "        #             x = math.lcm(p, num)\n",
    "        #             if k % x == 0:\n",
    "        #                 cur[x] = cur.get(x, 0) + pre[p]\n",
    "        #         ans += cur.get(k, 0)        \n",
    "        #     pre = cur\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cur = nums[i]\n",
    "            for j in range(i, n):\n",
    "                cur = lcm(cur, nums[j])\n",
    "                if cur > k:\n",
    "                    break\n",
    "                if cur == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            lcm = 1\n",
    "            for j in range(i,n):\n",
    "                lcm = lcm * nums[j] // gcd(lcm,nums[j])\n",
    "                if k % lcm:\n",
    "                    break\n",
    "                if lcm == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        def zxgb(zx_before, num):\n",
    "            save = zx_before\n",
    "            while zx_before % num != 0:\n",
    "                zx_before += save\n",
    "            return zx_before\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(len(nums)):\n",
    "            before = nums[i]\n",
    "            if before == k:\n",
    "                ret += 1\n",
    "            # print(nums[i], \"=======\")\n",
    "            for j in range(i+1, len(nums)):\n",
    "                new_zx = zxgb(before, nums[j])\n",
    "                before = new_zx\n",
    "                # print(new_zx)\n",
    "                if new_zx == k:\n",
    "                    ret += 1\n",
    "                elif new_zx > k: break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        #计算最小公倍数            \n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            if (a % b == 0):\n",
    "                return b\n",
    "            else:\n",
    "                return gcd(b, a % b)\n",
    "\n",
    "        def imax(a, b):\n",
    "            return a * b / gcd(a, b)\n",
    "        \n",
    "        l=len(nums)\n",
    "        if(l==0):\n",
    "            return 0\n",
    "        if(l==1):\n",
    "            if(k%nums[0]==0 and k/nums[0]==1):\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        \n",
    "        i,count=0,0\n",
    "        while i<l:\n",
    "            m=nums[i]\n",
    "            j=i\n",
    "            while j<l:\n",
    "                m=imax(m,nums[j])\n",
    "                if(m>k):\n",
    "                    break\n",
    "                if (m==k):\n",
    "                    count=count+1\n",
    "                j=j+1\n",
    "            i=i+1\n",
    "        return count\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        def gcd(x, y):\n",
    "            if x == 0:\n",
    "                return y\n",
    "            else:\n",
    "                return gcd(y % x, x)\n",
    "        for i in range(n):\n",
    "            last = nums[i]\n",
    "            for j in range(i, n):\n",
    "                g = last * nums[j] // gcd(last, nums[j]) \n",
    "                if g == k:\n",
    "                    res += 1\n",
    "                last = g\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break  # 剪枝：LCM 必须是 k 的因子\n",
    "                if res == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        def lcm(a, b):\n",
    "            ac, bc = a, b\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            while b % a:\n",
    "                r = b % a\n",
    "                b, a = a, r\n",
    "            return ac * bc // a\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            l = 1\n",
    "            for j in range(i, n):\n",
    "                l = lcm(l, nums[j])\n",
    "                if k % l:\n",
    "                    break\n",
    "                if k == l:\n",
    "                    res += 1\n",
    "        return res\n",
    "\n",
    "        # ans, n = 0, len(nums)\n",
    "        # for i in range(n):\n",
    "        #     res = 1\n",
    "        #     for j in range(i, n):\n",
    "        #         res = lcm(res, nums[j])\n",
    "        #         if k % res: break  # 剪枝：LCM 必须是 k 的因子\n",
    "        #         if res == k: ans += 1\n",
    "        # return ans\n",
    "\n",
    "        # ans = 0\n",
    "        # n = len(nums)\n",
    "        # pre = dict()\n",
    "        # for num in nums:\n",
    "        #     cur = dict()\n",
    "        #     if k % num == 0:\n",
    "        #         cur[num] = 1\n",
    "        #         for p in pre:\n",
    "        #             x = math.lcm(p, num)\n",
    "        #             if k % x == 0:\n",
    "        #                 cur[x] = cur.get(x, 0) + pre[p]\n",
    "        #         ans += cur.get(k, 0)        \n",
    "        #     pre = cur\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        def lcm(a, b):\n",
    "            ac, bc = a, b\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            while b % a:\n",
    "                r = b % a\n",
    "                b, a = a, r\n",
    "            return ac * bc // a\n",
    "        \n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            for j in range(i, len(nums)):\n",
    "                if i == j:\n",
    "                    l = nums[j]\n",
    "                else:\n",
    "                    # l = lcm(l, nums[j])\n",
    "                    l = math.lcm(l, nums[j])\n",
    "                if l == k:\n",
    "                    res += 1\n",
    "        return res\n",
    "\n",
    "        # ans = 0\n",
    "        # n = len(nums)\n",
    "        # pre = dict()\n",
    "        # for num in nums:\n",
    "        #     cur = dict()\n",
    "        #     if k % num == 0:\n",
    "        #         cur[num] = 1\n",
    "        #         for p in pre:\n",
    "        #             x = math.lcm(p, num)\n",
    "        #             if k % x == 0:\n",
    "        #                 cur[x] = cur.get(x, 0) + pre[p]\n",
    "        #         ans += cur.get(k, 0)        \n",
    "        #     pre = cur\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        # res = 0\n",
    "        \n",
    "        # def lcm(a, b):\n",
    "        #     ac, bc = a, b\n",
    "        #     if a > b:\n",
    "        #         a, b = b, a\n",
    "        #     while b % a:\n",
    "        #         r = b % a\n",
    "        #         b, a = a, r\n",
    "        #     return ac * bc // a\n",
    "        \n",
    "        # for i in range(len(nums)-1, -1, -1):\n",
    "        #     for j in range(i, len(nums)):\n",
    "        #         if i == j:\n",
    "        #             l = nums[j]\n",
    "        #         else:\n",
    "        #             l = lcm(l, nums[j])\n",
    "        #         if l == k:\n",
    "        #             res += 1\n",
    "        # return res\n",
    "\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        pre = dict()\n",
    "        for num in nums:\n",
    "            cur = dict()\n",
    "            if k % num == 0:\n",
    "                cur[num] = 1\n",
    "                for p in pre:\n",
    "                    x = math.lcm(p, num)\n",
    "                    if k % x == 0:\n",
    "                        cur[x] = cur.get(x, 0) + pre[p]\n",
    "                ans += cur.get(k, 0)        \n",
    "            pre = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math \n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        left, right =  0, 0\n",
    "        ans = 0\n",
    "        for r in range(len(nums)):\n",
    "            lcmCache = 1\n",
    "            for l in range(r, len(nums)):\n",
    "                lcmCache = math.lcm(lcmCache, nums[l])\n",
    "                if lcmCache > k:\n",
    "                    break\n",
    "                if lcmCache == k:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for a in accumulate(nums[i:], lcm):\n",
    "                if a > k:\n",
    "                    break\n",
    "                if a == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        def gcd(a, b):\n",
    "            while b != 0:\n",
    "                temp = a % b\n",
    "                a = b\n",
    "                b = temp\n",
    "            return a\n",
    "\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            temp = nums[i]\n",
    "            for j in range(i, n):\n",
    "                temp = temp * nums[j] // gcd(temp, nums[j])\n",
    "                if temp == k:\n",
    "                    res += 1\n",
    "                elif temp > k:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            temp = nums[i]\n",
    "            for j in range(i, n):\n",
    "                temp = lcm(temp, nums[j])\n",
    "                if temp == k:\n",
    "                    res += 1\n",
    "                elif temp > k:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res:\n",
    "                    break\n",
    "                if res == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        def find_lcm(a, b):\n",
    "            # 寻找两个数的最大公约数\n",
    "            def find_gcd(x, y):\n",
    "                while y:\n",
    "                    x, y = y, x % y\n",
    "                return x\n",
    "\n",
    "            # 两个数的最小公倍数等于它们的乘积除以最大公约数\n",
    "            lcm = (a * b) // find_gcd(a, b)\n",
    "            return lcm\n",
    "\n",
    "        tmp_l = []\n",
    "        for i in range(1,k+1):\n",
    "            if k%i == 0:\n",
    "                tmp_l.append(i)\n",
    "\n",
    "\n",
    "        n =len(nums)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            tmp = 1\n",
    "            for j in range(i,n):\n",
    "                if find_lcm(tmp,nums[j]) == k:\n",
    "                    ans +=1\n",
    "                elif find_lcm(tmp,nums[j]) not in tmp_l:\n",
    "                    break\n",
    "\n",
    "                tmp = find_lcm(tmp,nums[j])\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i,n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res:\n",
    "                    break\n",
    "                if res == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        pre = dict()\n",
    "        for num in nums:\n",
    "            cur = dict()\n",
    "            if k % num == 0:\n",
    "                cur[num] = cur.get(num, 0) + 1\n",
    "                for p in pre:\n",
    "                    x = math.lcm(p, num)\n",
    "                    if k % x == 0:\n",
    "                        cur[x] = cur.get(x, 0) + pre[p]\n",
    "                ans += cur.get(k, 0)        \n",
    "            pre = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        n = len(nums)\r\n",
    "        for i in range(n):\r\n",
    "            lcm = nums[i]\r\n",
    "            for j in range(i, n):\r\n",
    "                lcm = lcm * nums[j] // math.gcd(lcm, nums[j])\r\n",
    "                if lcm == k:\r\n",
    "                    ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ret=0\n",
    "        for i in range(len(nums)):\n",
    "            lcm=nums[i]\n",
    "            if lcm==k:\n",
    "                ret+=1\n",
    "            elif lcm>k:\n",
    "                continue\n",
    "            for j in range(i+1,len(nums)):\n",
    "                lcm=lcm*nums[j]//math.gcd(lcm,nums[j])\n",
    "                if lcm>k:\n",
    "                    break\n",
    "                elif lcm==k:\n",
    "                    ret+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        nums.append(k + 1)\n",
    "        res, N = 0, len(nums)\n",
    "        l = 0\n",
    "\n",
    "        #print(nums)\n",
    "        #print('================')\n",
    "\n",
    "        def lcm(a, b):\n",
    "            return a * b // math.gcd(a, b)\n",
    "\n",
    "\n",
    "        def resolve(l, r):\n",
    "            if r < l: return 0\n",
    "\n",
    "            res = 0\n",
    "\n",
    "            #print(l, r, '----------------')\n",
    "            for i in range(l, r + 1):\n",
    "                #print(i,'----------------')\n",
    "                tmp = nums[i]\n",
    "                for j in range(i, l - 1, -1):\n",
    "                    tmp = lcm(tmp, nums[j])\n",
    "                    #print(':', j, i ,'     ', nums[j], nums[i])\n",
    "                    if tmp == k:\n",
    "                        #print('add ',j)\n",
    "                        res += 1\n",
    "                    elif tmp > k:\n",
    "                        break\n",
    "\n",
    "            #print('-> ',res)\n",
    "            return res\n",
    "\n",
    "        \n",
    "        for r in range(N):\n",
    "            if k % nums[r] == 0:\n",
    "                continue\n",
    "            else:\n",
    "                res += resolve(l, r - 1)\n",
    "                l = r + 1\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for a in accumulate(nums[i:], lcm):\n",
    "                if a > k:\n",
    "                    break\n",
    "                if a == k:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        def lcm(m,n):return m*n//math.gcd(m,n)\n",
    "        r,s=0,[(True if k%n else False) for n in nums]\n",
    "        for i,n in enumerate(nums):\n",
    "            if s[i]:continue\n",
    "            l=n\n",
    "            for j in reversed(range(i+1)):\n",
    "                if s[j]:break\n",
    "                l=lcm(l,nums[j])\n",
    "                if l==k:r+=1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            LCM = 1\n",
    "            for j in range(i, n):\n",
    "                LCM = lcm(LCM, nums[j])\n",
    "                if LCM > k: break\n",
    "                if LCM == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            t = 1\n",
    "            for j in range(i,n):\n",
    "                t = lcm(t,nums[j])\n",
    "                if k % t:\n",
    "                    break\n",
    "                if t == k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break  # 剪枝：LCM 必须是 k 的因子\n",
    "                if res == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        nums.append(k + 1)\n",
    "        res, l = 0, 0\n",
    "\n",
    "        def resolve(l, r):\n",
    "            if r < l: return 0\n",
    "            res = 0\n",
    "            for i in range(l, r + 1):\n",
    "                tmp = nums[i]\n",
    "                for j in range(i, l - 1, -1):\n",
    "                    tmp = tmp * nums[j] // math.gcd(tmp, nums[j])\n",
    "                    if tmp == k:\n",
    "                        res += 1\n",
    "                    elif tmp > k:\n",
    "                        break\n",
    "            return res\n",
    "\n",
    "        \n",
    "        for r in range(len(nums)):\n",
    "            if k % nums[r] != 0:\n",
    "                res += resolve(l, r - 1)\n",
    "                l = r + 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        a = []  # [LCM，相同 LCM 区间的右端点]\n",
    "        i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if k % x:  # 保证后续求的 LCM 都是 k 的因子\n",
    "                a = []\n",
    "                i0 = i\n",
    "                continue\n",
    "            a.append([x, i])\n",
    "            # 原地去重，因为相同的 LCM 都相邻在一起\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = lcm(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "            del a[j + 1:]\n",
    "            if a[0][0] == k:\n",
    "                ans += a[0][1] - i0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        c=[]\n",
    "        ans=0\n",
    "        s=[]\n",
    "        def lcm(a,b):\n",
    "            for i in range(min(a,b),0,-1):\n",
    "                if a%i==0 and b%i==0:\n",
    "                    return (a*b)//i\n",
    "        for i in range(len(nums)):\n",
    "            s.append(int(nums[i]))\n",
    "        for i in range(len(s)):\n",
    "            if k%s[i]==0:\n",
    "                c.append(s[i])\n",
    "            elif len(c)!=0:\n",
    "        \n",
    "                t=0\n",
    "                while t!=len(c):\n",
    "                    key=1\n",
    "                    for j in range(t,len(c)):\n",
    "                        key=lcm(key,c[j])\n",
    "                        if key==k:\n",
    "                            ans+=(len(c)-j)\n",
    "                            break\n",
    "                    t+=1\n",
    "                c=[]\n",
    "        if len(c)!=0:\n",
    "            t=0\n",
    "            while t!=len(c):\n",
    "                key=1\n",
    "                for j in range(t,len(c)):\n",
    "                    key=lcm(key,c[j])\n",
    "                    if key==k:\n",
    "                        ans+=len(c)-j\n",
    "                        break\n",
    "                t+=1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            pre = 1\n",
    "            for j in range(i, n):\n",
    "                pre = math.lcm(pre, nums[j])\n",
    "                if pre == k:\n",
    "                    ans += 1\n",
    "                if pre > k or k % pre != 0:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        # 数组的最小公倍数：被所有数组元素整除的最小正整数\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1 \n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break # 剪枝\n",
    "                if res == k: ans += 1 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, arr: List[int], k: int) -> int:\n",
    "        st=[]\n",
    "        res=0\n",
    "        for i,a in enumerate(arr):\n",
    "            for j in range(len(st)):\n",
    "                st[j][0]=lcm(st[j][0],a)\n",
    "            nst=[]\n",
    "            for v,j in st:\n",
    "                if len(nst)==0 or v!=nst[-1][0]:\n",
    "                    nst.append([v,j])\n",
    "            nst.append([a,i])\n",
    "            if a==k:\n",
    "                res+=1\n",
    "            for j in range(len(nst)-1):\n",
    "                v,s,e=nst[j][0],nst[j][1],nst[j+1][1]-1\n",
    "                if v==k:\n",
    "                    res+=e-s+1\n",
    "            st=nst\n",
    "            if len(st)>1 and st[-1][0]==st[-2][0]:\n",
    "                st.pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            cur = 1\n",
    "            for j in range(i, len(nums)):\n",
    "                cur = lcm(cur, nums[j])\n",
    "                if cur==k:\n",
    "                    res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for a in accumulate(nums[i:], lcm):\n",
    "                if a > k:\n",
    "                    break\n",
    "                if a == k:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break  # 剪枝：LCM 必须是 k 的因子\n",
    "                if res == k: ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for myLCM in accumulate(nums[i:], lcm):\n",
    "                if k % myLCM != 0:\n",
    "                    break\n",
    "                if k == myLCM:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break  \n",
    "                if res == k: ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ##ST表？\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            cur=1\n",
    "            for j in range(i,n):\n",
    "                cur=lcm(cur,nums[j])\n",
    "                if k%cur!=0:\n",
    "                    break\n",
    "                if cur==k:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        def fun(x, y):\n",
    "            l, r = max(x, y), min(x, y)\n",
    "            q = l % r\n",
    "            while q != 0:\n",
    "                l, r = r, q\n",
    "                q = l % r\n",
    "            return int(x*(y/r))\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            p = nums[i]\n",
    "            if p == k:\n",
    "                ans += 1\n",
    "            j = i+1\n",
    "            while j < len(nums) and p <= k:\n",
    "                p = fun(p, nums[j])\n",
    "                if p == k:\n",
    "                    ans += 1\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                # if k % res: \n",
    "                    # break  # 剪枝：LCM 必须是 k 的因子\n",
    "                if res == k: \n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        def computeLCM(a: int, b: int) -> int:\n",
    "            return abs(a*b) // gcd(a,b)\n",
    "        \n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            currLCM = nums[i]\n",
    "            for j in range(i, n):\n",
    "                currLCM = computeLCM(currLCM, nums[j])\n",
    "                if currLCM == k:\n",
    "                    count += 1\n",
    "                # 如果当前LCM已经大于k，没有继续检查的意义\n",
    "                if currLCM > k:\n",
    "                    break\n",
    "                    \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i,n):\n",
    "                res = math.lcm(res, nums[j])\n",
    "                if res==k: ans += 1\n",
    "                if not k%res==0: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break\n",
    "                if res == k: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            res = 1\n",
    "            for j in range(i, n):\n",
    "                res = lcm(res, nums[j])\n",
    "                if k % res: break  # 剪枝：LCM 必须是 k 的因子\n",
    "                if res == k: ans += 1\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        a = []  # [LCM，相同 LCM 区间的右端点]\n",
    "        i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if k % x:  # 保证后续求的 LCM 都是 k 的因子\n",
    "                a = []\n",
    "                i0 = i\n",
    "                continue\n",
    "            a.append([x, i])\n",
    "            # 原地去重，因为相同的 LCM 都相邻在一起\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = lcm(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "            del a[j + 1:]\n",
    "            if a[0][0] == k:\n",
    "                ans += a[0][1] - i0\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/number-of-subarrays-with-lcm-equal-to-k/description/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        ##ST表？\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            cur=1\n",
    "            for j in range(i,n):\n",
    "                cur=lcm(cur,nums[j])\n",
    "                if cur==k:\n",
    "                    ans+=1\n",
    "                elif k%cur!=0:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        count,n=0,len(nums)\n",
    "        for i in range(n):\n",
    "            m=1\n",
    "            for j in range(i,n):\n",
    "                m=lcm(m,nums[j])\n",
    "                if m>k:break\n",
    "                if m==k:count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        dp = [0] * len(nums)\n",
    "        \n",
    "        def lcm(a, b):\n",
    "            ac, bc = a, b\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            while b % a:\n",
    "                r = b % a\n",
    "                b, a = a, r\n",
    "            return ac * bc // a\n",
    "        \n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            for j in range(i, len(nums)):\n",
    "                if i == j:\n",
    "                    dp[j] = nums[j]\n",
    "                else:\n",
    "                    dp[j] = lcm(dp[j-1], nums[j])\n",
    "                if dp[j] == k:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        def gcd(a, b):\n",
    "\n",
    "            while b:\n",
    "                temp = a % b\n",
    "                a = b\n",
    "\n",
    "                b = temp\n",
    "            return int(a)\n",
    "\n",
    "        def lcm(a, b):\n",
    "            return int(a * b / gcd(a, b))\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            res = 1\n",
    "            for j in range(i, len(nums)):\n",
    "                res = lcm(res, nums[j])\n",
    "\n",
    "                if k %  res:\n",
    "                    break\n",
    "                \n",
    "                if res == k:\n",
    "                    print(nums[j])\n",
    "                    ans += 1\n",
    "\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "A=list()\n",
    "for i in range(2,1001):\n",
    "    flag=0\n",
    "    for j in A:\n",
    "        if i%j==0:\n",
    "            flag=1\n",
    "    if flag==0:\n",
    "        A.append(i)\n",
    "dic=dict()\n",
    "for s in range(1,1001):\n",
    "    now=dict()\n",
    "    x=s\n",
    "    for i in A:\n",
    "        while x%i==0:\n",
    "            x=x//i\n",
    "            now[i]=now.get(i,0)+1\n",
    "        if x==1:\n",
    "            break\n",
    "    dic[s]=now     \n",
    "class Solution:\n",
    "    def subarrayLCM(self, nums: List[int], k: int) -> int:\n",
    "        count=0\n",
    "        for i in range(len(nums)):\n",
    "            now=dict()\n",
    "            x=i\n",
    "            flag=0\n",
    "            while x<len(nums) and flag==0:\n",
    "                for j in dic[nums[x]]:\n",
    "                    now[j]=max(now.get(j,0),dic[nums[x]][j])\n",
    "                    if now[j]>dic[k].get(j,0):\n",
    "                        flag=1\n",
    "                        break\n",
    "                if now==dic[k]:\n",
    "                    count+=1\n",
    "                x+=1\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
